/*
 *  $Id: StringGrouper.cs 1170 2010-11-05 15:29:39Z thenn.erannor $
 *	This file is a part of Ragima CCG.
 *	(C) 2008-2010 Ragima development group.
 *
 *	Licensed under the terms of the GNU GPL License version 2.
 *
 */

using System;
using System.Text;

namespace Ragima.Helper {
    /// <summary>
    /// Класс для группировки/разгруппировки строк.
    /// </summary>
    public class StringGrouper {
        /// <summary>
        /// Экземпляр со стандартными символами группировки строк: группы в скобках, части разделены запятыми.
        /// </summary>
        public static readonly StringGrouper Default = new StringGrouper('(', ')', ',');

        private char _groupStart, _groupEnd, _delimiter;

        /// <summary>
        /// Создает экземпляр StringGrouper с указанными символами.
        /// </summary>
        /// <param name="groupStart">Символ начала группы.</param>
        /// <param name="groupEnd">Символ конца группы.</param>
        /// <param name="delimiter">Символ-разделитель частей внутри группы.</param>
        public StringGrouper(char groupStart, char groupEnd, char delimiter) {
            _groupStart = groupStart;
            _groupEnd = groupEnd;
            _delimiter = delimiter;
        }

        /// <summary>
        /// Разгруппирует строки из общего шаблона.
        /// </summary>
        /// <param name="template">Сгруппированная строка-шаблон.</param>
        /// <param name="count">Количество итоговых строк.</param>
        /// <returns>Массив итоговых строк.</returns>
        public string[] Ungroup(string template, int count) {
            // Проверка входных параметров
            if (template == null || count <= 0)
                return null;

            // Подготовка массива StringBuilder'ов
            var len = template.Length;
            var strings = new StringBuilder[count];
            for (int i = 0; i < count; i++)
                strings[i] = new StringBuilder(len);

            // Цикл по строке-шаблону
            var pos = 0;
            while (pos < len) {
                // Поиск символа начала группы
                var start = FindChar(_groupStart, template, pos, len);
                // Если начало группы не в текущей позиции, то добавление данной части шаблона во все строки
                if (start != pos) {
                    for (int i = 0; i < count; i++)
                        strings[i].Append(template, pos, start - pos);
                }
                start++;

                // Выход, если начало группы не найдено
                if (start >= len)
                    break;

                // Поиск символа конца группы
                var end = FindChar(_groupEnd, template, start, len);

                // Цикл по строкам, пока не конец группы
                for (int i = 0; i < count && start < end; i++) {
                    // Поиск символа-разделителя
                    pos = FindChar(_delimiter, template, start, end);
                    // Если часть группы не пустая, то добавление её в текущую строку
                    if (pos != start)
                        strings[i].Append(template, start, pos - start);
                    // Установка начала поиска на следующую часть группы
                    start = pos + 1;
                }

                // Обновление текущей позиции
                pos = end + 1;
            }

            // Получение строк по StringBuilder'ам
            return Array.ConvertAll(strings, sb => sb.ToString());
        }

        /// <summary>
        /// Ищет символ в указанном отрезке строки. Если символ не найден, то возвращает не -1, а конец отрезка.
        /// </summary>
        /// <param name="search">Искомый символ.</param>
        /// <param name="s">Строка, в которой искать.</param>
        /// <param name="start">Начальная позиция поиска</param>
        /// <param name="end">Конечная позиция поиска.</param>
        /// <returns>Найденная позация, либо конечная, если символ не найден.</returns>
        private static int FindChar(char search, string s, int start, int end) {
            var i = start;
            while (i < end && s[i] != search)
                i++;
            return i;
        }

        /// <summary>
        /// Группирует набор строк в одну общую строку-шаблон, находя и объединяя общие части строк.
        /// </summary>
        /// <param name="strings">Входной набор строк.</param>
        /// <returns>Итоговая строка-шаблон.</returns>
        public string Group(string[] strings) {
            // Проверка входных параметров
            if (strings == null || strings.Length == 0)
                return null;

            // Если в наборе лишь одна строка, то просто её возврат
            if (strings.Length == 1)
                return strings[0];

            // Создание билдера и набора подстрок, являющихся полными исходными строками
            var sb = new StringBuilder();
            var parts = Array.ConvertAll(strings, s => new Substring(s));

            // Запуск основного алгоритма
            DoGroup(sb, parts);

            // Получение строки
            return sb.ToString();
        }

        /// <summary>
        /// Выполняет одну итерацию алгоритма группировки строк.
        /// </summary>
        /// <param name="builder">Билдер для построения общей строки.</param>
        /// <param name="parts">Набор подстрок.</param>
        private void DoGroup(StringBuilder builder, Substring[] parts) {
            // Если все подстроки пустые, то выход без каких-либо действий
            if (Array.TrueForAll(parts, s => s.Length == 0))
                return;

            // Поиск наибольшей общей подстроки
            var lcs = FindLCS(parts);

            // Если общая подстрока не найдена, то построение группы и выход
            if (lcs.Length == 0) {
                BuildGroup(builder, parts);
                return;
            }

            // Получение частей строк слева от найденной общей подстроки
            var newParts = new Substring[parts.Length];
            for (int i = 0; i < parts.Length; i++)
                newParts[i] = new Substring(parts[i].Value, parts[i].Start, lcs.Starts[i] - parts[i].Start);
            // Рекурсивный вызов алгоритма для левых частей
            DoGroup(builder, newParts);

            // Добавление найденной общей подстроки
            builder.Append(parts[0].Value, lcs.Starts[0], lcs.Length);

            // Получение частей строк справа от найденной общей подстроки
            for (int i = 0; i < parts.Length; i++) {
                var lcsEnd = lcs.Starts[i] + lcs.Length;
                newParts[i] = new Substring(parts[i].Value, lcsEnd, parts[i].End - lcsEnd);
            }
            // Рекурсивный вызов алгоритма для правых частей
            DoGroup(builder, newParts);
        }

        /// <summary>
        /// Ищет наибольшую общую подстроку в наборе строк.
        /// </summary>
        /// <param name="parts">Набор строк./param>
        /// <returns>Структура с данными об общей подстроке./returns>
        private StringCommonPart FindLCS(Substring[] parts) {
            // Если хоть одна строка пустая, то общей подстроки нет
            if (Array.Exists(parts, s => s.Length == 0))
                return new StringCommonPart(0);

            // Подготовка начальных данных для поиска
            var lcs = new StringCommonPart(parts);
            var current = parts[0];

            // Цикл по строкам (начиная со второй, так как первая в current)
            for (int i = 1; i < parts.Length; i++) {
                // Поиск общей подстроки между current и текущей строкой цикла
                var tlcs = FindLCS(current, parts[i]);
                // Установка длины найденной подстроки
                lcs.Length = tlcs.Length;
                // Выход, если общая подстрока не найдена
                if (lcs.Length == 0)
                    break;

                // Установка начала подстроки в текущей строке цикла
                lcs.Starts[i] = tlcs.Start2;
                // Обновление начала подстрок во всех уже обработанных строках, если оно изменилось
                if (tlcs.Start1 > current.Start)
                    for (int j = 1; j < i; i++)
                        lcs.Starts[j] += tlcs.Start1 - current.Start;
                // Установка начала подстроки в первой строке
                lcs.Starts[0] = tlcs.Start1;
                // Установка найденной подстроки в current для дальнейшего поиска
                current = new Substring(current.Value, tlcs.Start1, tlcs.Length);
            }

            // Возврат результатов
            return lcs;
        }

        /// <summary>
        /// Ищет наибольшую общую подстроку в двух строках.
        /// </summary>
        /// <param name="s1">Первая строка.</param>
        /// <param name="s2">Вторая строка.</param>
        /// <returns>Структура с данными об общей подстроке.</returns>
        private TwoStringCommonPart FindLCS(Substring s1, Substring s2) {
            // Подготовка рабочих данных
            var lcs = new TwoStringCommonPart();
            var table = new int[s1.Length + 1, s2.Length + 1];

            // Цикл по первой строке
            for (int i = 0; i < s1.Length; i++) {
                // Цикл по втокой строке
                for (int j = 0; j < s2.Length; j++) {
                    // Если текущие символы в обоих строках равны, то увеличение длины общей подстроки
                    if (s1.Value[s1.Start + i] == s2.Value[s2.Start + j]) {
                        // Увеличение длины общей подстроки
                        var length = table[i, j] + 1;
                        table[i + 1, j + 1] = length;

                        // Если длина текущей подстроки больше чем ранее найденная, то обновление данных о найденной подстроке на текущие
                        if (length > lcs.Length) {
                            lcs.Start1 = s1.Start + i + 1 - length;
                            lcs.Start2 = s2.Start + j + 1 - length;
                            lcs.Length = length;
                        }
                    }
                }
            }

            // Возврат результатов
            return lcs;
        }

        /// <summary>
        /// Строит группу строк с учетом символов.
        /// </summary>
        /// <param name="builder">Билдер для построения.</param>
        /// <param name="parts">Набор строк.</param>
        private void BuildGroup(StringBuilder builder, Substring[] parts) {
            builder.Append(_groupStart);
            for (int i = 0; i < parts.Length; i++) {
                if (i > 0)
                    builder.Append(_delimiter);
                builder.Append(parts[i].Value, parts[i].Start, parts[i].Length);
            }
            builder.Append(_groupEnd);
        }

        /// <summary>
        /// Структура с данными о подстроке.
        /// Используется для исключения создания множества объектов строк в процессе группировки.
        /// </summary>
        private struct Substring {
            public readonly string Value;
            public readonly int Start, Length;

            public Substring(string value) {
                Value = value;
                Start = 0;
                Length = value.Length;
            }

            public Substring(string value, int start, int length) {
                Value = value;
                Start = Math.Max(Math.Min(start, value.Length), 0);
                Length = Math.Min(length, value.Length - Start);
            }

            public int End {
                get { return Start + Length; }
            }
        }

        /// <summary>
        /// Структура с данными об общей подстроке в наборе строк.
        /// </summary>
        private struct StringCommonPart {
            public readonly int[] Starts;
            public int Length;

            public StringCommonPart(int count) {
                Starts = count > 0 ? new int[count] : null;
                Length = 0;
            }
            public StringCommonPart(Substring[] parts) {
                Starts = Array.ConvertAll(parts, s => s.Start);
                Length = 0;
            }
        }

        /// <summary>
        /// Структура с данными об общей подстроке в двух строках.
        /// </summary>
        private struct TwoStringCommonPart {
            public int Start1, Start2, Length;
        }
    }
}
